#include <bits/stdc++.h>

using namespace std;

// 数组中有2种数出现了奇数次，其他的数都出现了偶数次
// 返回这2种出现了奇数次的数
// 测试链接 : https://leetcode.cn/problems/single-number-iii/

class Solution 
{
public:
    vector<int> singleNumber(vector<int>& nums) 
    {
        long eor1 = 0; // 避免溢出
        // nums中有2种数a、b出现了奇数次，其他的数都出现了偶数次
        for(int x : nums) eor1 ^= x;
        // eor1 : a ^ b
		// Brian Kernighan算法
		// 提取出二进制里最右侧的1
        int rightOne = eor1 & (-eor1);
        int eor2 = 0;
        for(int x : nums)
        {
            if((x & rightOne) == 0) eor2 ^= x;
        }
        return {eor2, (int)eor1 ^ eor2};
    }
};